Many error detecting and correcting codes have been proposed heretofore, and there are many patents relating to various error detection and correction systems. Perhaps the simplest error detection system involves the repetition of each digit of a transmitted message, with a lack of identity of two successive digits indicating the presence of an error. Similarly, for error correction, the digit may be repeated three times, and the correct digit determined by a "voting" circuit. Of course, more sophisticated error detection and correction circuits have been proposed, and these have involved what are known as parity check circuits. More specifically, additional error detection or correction bits may be added to groups of digits so that their sum when transmitted is always even, or always odd. Then, at the receiving station, a similar sum may be made, and if there is a change in parity, an error is present.
A moderately sophisticated error correction circuit is disclosed in B. K. Betz, U.S. Pat. No. 3,387,261. In this patent, a system is disclosed for correcting errors through the use of two parity check bits, one taken horizontally through a digital word, and the second taken diagonally through successive digits of adjacent words in a matrix of information. An error in one bit of the information will produce an error in parity in one of the vertical error correction parity bits, and also in one of the diagonal parity bits, and the two error correction bits together will uniquely identify the erroneous information bit, and it can then be corrected.
One problem with the system disclosed in the Betz patent, as well as with many of the other systems which have previously been proposed, is that they characteristically require excessive redundancy relative to their capabilities for correcting data.
Accordingly, a principal object of the present invention is to increase the error detection and error correction capability of data processing circuits, without significantly increasing the amount of data which must be transmitted over the data transmission link.